package Test;

import java.util.List;

public class K个一组反转链表 {
    class ListNode{
        int val;
        ListNode next;
        ListNode(int val){
            this.val=val;
        }
    }

    public ListNode reverseKGroup(ListNode head, int k) {
        ListNode a=head,b=head;
        for (int i=0;i<k;i++){
            if(b==null){
                return head;
            }
            b=b.next;

        }
        ListNode newHead=reverse(a,b);
        a.next=reverseKGroup(b,k);
        return newHead;
    }

    ListNode reverse(ListNode a,ListNode b){


        ListNode pre,nxt;
        pre=null;
        while (a!=b){
            nxt=a.next;
            a.next=pre;
            pre=a;
            a=nxt;
        }
        return pre;
    }

    public ListNode reverseKGroup1(ListNode head, int k) {
        ListNode a,b;
        a=b=head;
        for (int i=0;i<k;i++){
            b=b.next;
            if(b==null){
                return head;
            }
        }
        ListNode last=reverse1(a,b);
        a.next=reverseKGroup1(b,k);
        return last;
    }


    ListNode reverse1(ListNode a,ListNode b){
        ListNode pre,nxt;
        pre=null;
        while (a!=b){
            nxt=a.next;
            a.next=pre;
            pre=a;
            a=nxt;
        }
        return a;
    }
}
